package main

import (
	"fmt"
	. "local/algorithm/util"
	"math"
)

func maxPathSum(root *TreeNode) int {
	sum := math.MinInt32
	var oneSide func(root *TreeNode) int
	oneSide = func(root *TreeNode) int {
		if root == nil {
			return 0
		}

		left := oneSide(root.Left)
		right := oneSide(root.Right)
		currMax := max(max(left+root.Val, root.Val+right), root.Val)
		sum = max(sum, max(currMax, root.Val+left+right))
		return currMax
	}
	oneSide(root)
	return sum
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	root := &TreeNode{Val: 1}
	fmt.Println(maxPathSum(root))
}
